TNotes.leetcode

Appearance

0415. 字符串相加【简单】

0415. 字符串相加【简单】 ​

1. 📝 题目描述 ​

给定两个字符串形式的非负整数 num1 和num2，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例 1：

txt
输入：num1 = "11", num2 = "123"
输出："134"

示例 2：

txt
输入：num1 = "456", num2 = "77"
输出："533"

示例 3：

txt
输入：num1 = "0", num2 = "0"
输出："0"

提示：

  • 1 <= num1.length, num2.length <= 10^4
  • num1 和num2 都只包含数字 0-9
  • num1 和num2 都不包含任何前导零

2. 🎯 s.1 - 模拟十进制逐位相加 ​

js
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var addStrings = function (num1, num2) {
  let i = num1.length - 1
  let j = num2.length - 1
  let carry = 0
  let result = ''

  // 从末尾开始逐位相加
  while (i >= 0 || j >= 0 || carry > 0) {
    let digit1 = i >= 0 ? parseInt(num1[i]) : 0
    let digit2 = j >= 0 ? parseInt(num2[j]) : 0

    let sum = digit1 + digit2 + carry
    carry = Math.floor(sum / 10)
    result = (sum % 10) + result

    i--
    j--
  }

  return result
}
  • 时间复杂度：O(max(m,n))，其中 m 和 n 分别是两个字符串的长度，需要遍历较长字符串的每一位
  • 空间复杂度：O(max(m,n))，用于存储结果字符串
  • 算法思路：
    • 利用两个指针 i、j，分别指向 nums 和 num2 的末尾位置，从最低位开始逐位相加，用 carry 来记录进位，用 result 来记录最终结果。
  • 模拟手工加法的过程：
    1. 从两个字符串的末尾开始逐位相加
    2. 处理进位情况
    3. 将每一位的计算结果添加到结果字符串中
    4. 注意处理两个字符串长度不同的情况

Discussions